package cn.leecode.q28;


/**
 * 28. 找出字符串中第一个匹配项的下标
 * 简单
 * 相关标签
 * 相关企业
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 * 示例 1：
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 * 示例 2：
 * 输入：haystack = "leetcode", needle = "leeto"
 * 输出：-1
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 * 提示：
 * 1 <= haystack.length, needle.length <= 104
 * haystack 和 needle 仅由小写英文字符组成
 */
public class StringFirstMatchIndex {
    /**
     * 在一个字符串（haystack）中查找另一个字符串（needle）的第一次出现的位置
     *
     * @param haystack 主字符串，在这个字符串中查找needle
     * @param needle 需要查找的字符串
     * @return 如果找到needle，则返回它在haystack中第一次出现的索引；如果未找到，则返回-1
     */
    public int strStr(String haystack, String needle) {
        // 遍历haystack中的每个字符
        for (int i = 0; i < haystack.length(); i++) {
            // 获取当前字符
            char c = haystack.charAt(i);
            // 如果当前字符与needle的首字符相同，进一步检查是否找到了needle
            if (c == needle.charAt(0)) {
                // 初始化needle的索引
                int j = 0;
                // 遍历needle中的每个字符，检查是否完全匹配
                for (; j < needle.length(); j++) {
                    // 如果超出haystack的长度或字符不匹配，则终止检查
                    if (i + j >= haystack.length() || haystack.charAt(i + j) != needle.charAt(j)) {
                        break;
                    }
                }
                // 如果j等于needle的长度，说明找到了完整的needle
                if (j == needle.length()) {
                    // 返回needle在haystack中开始出现的位置
                    return i;
                }
            }
        }
        // 如果未找到needle，返回-1
        return -1;
    }


    public static void main(String[] args) {
        StringFirstMatchIndex stringFirstMatchIndex = new StringFirstMatchIndex();
        System.out.println(stringFirstMatchIndex.strStr("sadbutsad", "sad"));
        System.out.println(stringFirstMatchIndex.strStr("leetcode", "leeto"));
    }
}
